package com.example.demo.程序员面试金典;

/**
 * @description: TODO
 * @author: zhangzc
 * @modified By: zhangzc
 * @date: Created in 2022/9/8 14:34
 * @version:v1.0
 */
public class 三步问题 {

	public int waysToStep(int n) {
		if (n == 1) {
			return 1;
		}
		if (n == 2) {
			return 2;
		}
		if (n == 3) {
			return 4;
		}
		return waysToStep(n - 1) + waysToStep(n - 2) + waysToStep(n - 3);
	}

	// todo
	class Solution {

		//递推法。f(n)=f(n-1)+f(n-2)+f(n-3)

		public int waysToStep(int n) {
			if (n < 3) {
				return n;
			}

			int a = 1, b = 2, c = 4;
			for (int i = 4; i <= n; ++i) {
				int t = a;
				a = b;
				b = c;
				c = ((a + b) % 1000000007 + t) % 1000000007;
			}
			return c;
		}
	}

}
